Introduction
لو حابب تشوف نفس الملخص بتجربة افضل اضغط هنا
int n = 5;if(n && log(n)) => O(n)for(int i = 1; i <= n; i++)
print i;
// or
for(int i = n; i >= 1; i--)
print i;
for(int i = 1; i <= n; i*=2)
print i;
// or
for(int i = n; i >= 1; i/=2)
print i;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
print i;
for(int i = 1; i <= n; i*=3)
for(int j = 1; j <= n; j++)
print i;
for(int i = 1; i <= n; i*=3)
for(int j = 1; j <= n; j*=3)
print i;
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
print i;
Asymptotic notations describe the growth rate of an algorithm's running time as the input size
Example: If
Example: If
Example: If
زيها زي الO والاوميجا العاديين بس مفيهاش كلمة يساوي
if you're asked is
الـ Groth rate عكس ال time
Any recursive function has time in the following format:
int fact(int n){
if(n == 0) return 0;
else return fact(n - 1);
}
// or
int fact(int n){
if(n == 0) return 0;
else return n * fact(n - 1);
}
int fact(int n){
if(n == 0) return 0;
else return fact(n/2);
}
int fact(int n){
if(n == 0) return 0;
else return fact(n/2) + fact(n/2);
}
int fact(int n){
if(n == 0) return 0;
else return fact(n/2) + fact(3n/2);
}
int fact(int n){
if(n == 0){
for(int i = 1; i <= n; i++) {
cout << i;
}
return 1;
}
else return fact(n - 1) + fact(n - 2);
}
بتحل بعض انواع ال Recursion مش بيشتغل غير على المعادلات اللي بالشكل التالي
The recursion tree method is a visual way to analyze recurrence relations by expanding them level by level and summing up the work done at each level. This helps us find the overall complexity of an algorithm.
Each call to
بما إن كل مره بنقسم على 2 وهنوصل لـ 0 فالاخر فا الـ height =
انما لو كنا بنطرح 1 او رقم ثابت فا ال hight =
كل عنصر بيساوي اللي قبله مضروب في ثابت
كل عنصر بيساوي اللي قبله مجموع عليه ثابت, هنحاول نحطها على شكل قانون ال sum
The substitution method is a powerful technique for solving recurrence relations by:
Expanding the recurrence for a few levels:
The recursion stops when
The summation simplifies:
Expanding for a few values:
Continuing this process, after
If we assume the base case is
Substituting
Space complexity measures the total memory used by an algorithm as a function of the input size
هنا هنحسب عادي ولكن هنهتم فقط بالسطور اللي بخزن فيها داتا فالميموري, كمثال
int x = 5; // 1
int y = 7 // 2
int z = x + y; // 3
cout << z;
// Total = O(1)
الموضوع بسيط ولكن فيه شوية تريكات فال recursive functions
مكان فالميموري بيخزن الfunction والstatic variables شغال بمبدأ الـLast in first out
شرح تفصيلي فالفيديو الخاص بالدكتور اضغط هنا
Each recursive call adds a new function frame to the call stack, increasing space usage. For a recurrence like:
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) { // 1
cout << arr[i] << " ";
}
}
void recursiveFunc(int n) {
if (n == 0) return;
recursiveFunc(n - 1);
}
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
The recursive Fibonacci function makes two calls, but they are not executed simultaneously. The recursion first fully evaluates
The algorithm checks each element in an array one by one.
int linearSearch(int arr[], int n, int target) {
// Loop through each element of the array
for (int i = 0; i < n; i++) {
// Check if the current element matches the target
if (arr[i] == target) {
return i; // Return the index if found
}
}
return -1; // Return -1 if the target is not found
}
Binary search is an efficient algorithm for finding a target element in a sorted array.
it works by repeatedly dividing the search interval in half. If the target value is less than the value in the middle of the interval, the algorithm continues on the lower half. Otherwise, it continues on the upper half. This process repeats until the target is found or the search interval is empty.
int binarySearchRecursive(int arr[], int low, int high, int target) {
if (low > high)
return -1;
int mid = (high + mid) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, high, target);
return binarySearchRecursive(arr, low, mid - 1, target);
}
Insertion Sort is a simple and efficient sorting algorithm.
It builds the sorted sequence one element at a time by picking the next element and placing it in its correct position within the already sorted part.
1) because a single element (index 0) is already sorted.void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Selection Sort is a simple comparison-based sorting algorithm. The idea is to repeatedly select the minimum (or maximum) element from the unsorted part of the array and move it to the correct sorted position.
0.arr[i] to arr[n-1].arr[i].i + 1) and repeat until the array is sorted.void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
Quick Sort follows the Divide and Conquer strategy:
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Merge Sort is a Divide and Conquer algorithm:
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Counting Sort is a non-comparison sorting algorithm ideal for sorting integers within a known, limited range.
Instead of comparing elements, it:
void countSort(vector<int>& arr) {
int max_val = *max_element(arr.begin(), arr.end());
// Step 1: Create and initialize count array
vector<int> count(max_val + 1, 0);
// Step 2: Store count of each element
for (int num : arr)
count[num]++;
// Step 3: rebuild the sorted array
int k = 0;
for (int i = 0; i <= max_val; i++) {
for (int j = 0; j < count[i]; j++){
arr[k++] = i;
}
}
}
| Algorithm | Time Complexity (Best / Avg / Worst) | Space | In-Place | Stable | Notes |
|---|---|---|---|---|---|
| Linear Search | ✅ | ✅ | Works on unsorted data | ||
| Binary Search | ✅ | ✅ | Requires sorted data |
| Algorithm | Time Complexity (Best / Avg / Worst) | Space | In-Place | Stable | Notes |
|---|---|---|---|---|---|
| Selection Sort | ✅ | ❌ | Simple, always |
||
| Insertion Sort | ✅ | ✅ | Fast on nearly sorted arrays | ||
| Quick Sort | ✅ | ❌ | Fast in practice, not stable | ||
| Merge Sort | ❌ | ✅ | Very predictable, uses extra space | ||
| Count Sort | ❌ | ✅ | Only for integers / small range |
Algorithm design techniques are systematic approaches to solving computational problems efficiently.
يعني لما يجيلك سؤال أو مشكلة في البرمجة، مش لازم تبدأ تحل كده من دماغك وخلاص… لأ، فيه طرق معينة، كل طريقة ليها طريقة تفكير بتخليك توصل لحل سريع ومنظّم.
هو أسهل وأبسط طريقة لحل أي مشكلة… بتجرّب كل الحلول الممكنة لحد ما تلاقي الصح
تستخدمه لو حجم المشكلة عندك صغير ومفيهاش عناصر كتير، او لو مفيش حل افضل واسرع من ده، او لو عايز تكتب الكود بتاعه بسرعه، او لو عندك حل تاني بطريقة تانية وعايز تتاكد انه صح فا بتستخدم البروت فورس عشان تقارن بين الناتج بتاع الالجورذم التانية وبين الناتج بتاعه
الtime complexity بتبقى غالبا سيئة جدا جدا
تنفع تتنفذ بشكل متوازي، أو ممكن نوزّع شغلها على أكتر من معالج/كور (CPU cores) في نفس الوقت.
معناها إنك لما تواجه مشكلة كبيرة، بدل ما تحلها مرة واحدة، تقسمها لمشاكل أصغر (دي مرحلة الـ "Divide")، وتحل كل واحدة لوحدها غالبًا باستخدام Recursion (دي مرحلة الـ "Conquer")، وبعد كده تدمج نتايج الحلول الصغيرة دي مع بعض علشان تطلع حل المشكلة الأصلية (ودي مرحلة الـ "Combine"). الطريقة دي ممتازة لو المشكلة ممكن تتقسم وأجزاءها مش متداخلة، وبيكون فيها كفاءة عالية خاصة في المسائل اللي ينفع نحلها بشكل متوازي. أمثلة معروفة زي Merge Sort وBinary Search بيعتمدوا على نفس الفكرة دي
هي طريقة حل بتشتغل خطوة بخطوة، وفي كل خطوة بتختار أحسن حل ظاهر قدامك دلوقتي، على أمل إن الاختيارات دي كلها في الآخر توصلنا لأفضل حل نهائي. الميزة إنها سريعة وبسيطة، بس العيب إنها مش بترجع تصلّح نفسها، يعني لو أخدت قرار غلط خلاص بتكمل عليه علشان كده مش بتنفع مع كل المشاكل، إلا لو المشكلة فيها خاصيتين مهمين، أولًا إن الحل النهائي بيتكوّن من حلول مثالية لأجزاء صغيرة (دي بنسميها optimal substructure)، وثانيا إن الحل الأمثل النهائي ممكن نوصله عن طريق اختيارات مثالية محلية (greedy choice property)
ال Overlapping Subproblems يعني وانت بتحل المشكلة بتلاقي إن في نفس الجزء بيتحسب أكتر من مرة والمشكلة فيها تكرار لحسابات حصلت قبل كده، وممكن نخزّن النتايج دي بدل ما نحسبها تاني ونبقى نستخدمها لما نحتاجها بعدين
هي طريقة لحل مشاكل بتتكرر فيها نفس الخطوات كذا مرة، فبدل ما نعيد الحساب كل شوية، بنحسب الحاجة مرة واحدة ونخزّن النتيجة (دي فكرة "الذاكرة"). الطريقة دي بتشتغل كويس في المشاكل اللي فيها subproblems بتتكرر، فيه طريقتين نحل بيهم: يا إما Top-down (وده بالـ Recursion + Memoization، يعني بننزل للمشكلة الصغيرة ونرجع بالنتايج)، أو Bottom-up (وده بنبدأ من أصغر مشكلة ونطلع لفوق خطوة خطوة في جدول)
الDP بيبقى مفيد جدًا لما يكون الحل العادي (زي الـ Recursion) بياخد وقت كبير جدًا، زي في مشاكل الـ Fibonacci، knapsack، وlongest common subsequence
Calculate the
int fib(int n) {
if(n == 0 || n == 1) return n;
return fib(n-1) + fib(n-2);
}
For Fibonacci, a pure divide and conquer approach would be similar to the brute force recursive solution.
However, we can use matrix exponentiation which is a more efficient divide and conquer strategy.
The Fibonacci sequence doesn't naturally lend itself to a greedy approach since:
int fib(int n) {
if(n == 0 || n == 1) return n;
int a = 0, b = 1, temp;
for (int i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
int arr[n + 1]; // -> initilize by -1
int fib(int n) {
if(n == 0 || n == 1) return n;
if(arr[n] != -1) return arr[i];
arr[n] = fib(n-1) + fib(n-2);
return arr[n];
}
int fib(int n) {
int dp[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return arr[n];
}
نفس ال iterative فوق، بس ده في حالة الfibonacci بس
depends on the specific problem characteristics: